/*
https://leetcode.cn/problems/number-of-islands/submissions/583043220/
岛屿数量
并查集+一二维转换
*/
class Solution {
public:
    static const int MAXSIZE = 100001;  // 最大的数组大小
    int father[MAXSIZE];                // 并查集的父节点数组
    int cols;                           // 存储列数
    int sets;                           // 存储岛屿数量

    // 主函数，返回岛屿数量
    int numIslands(vector<vector<char>>& board) {
        int n = board.size();
        int m = board[0].size();
        build(n, m, board);  // 初始化并查集
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == '1') {
                    // 尝试与左边和上边相邻的 '1' 进行合并
                    if (j > 0 && board[i][j - 1] == '1') {
                        unionSets(i, j, i, j - 1);
                    }
                    if (i > 0 && board[i - 1][j] == '1') {
                        unionSets(i, j, i - 1, j);
                    }
                }
            }
        }
        return sets;  // 返回最后的岛屿数量
    }

private:
    // 初始化并查集
    void build(int n, int m, vector<vector<char>>& board) {
        cols = m;
        sets = 0;  // 初始化岛屿数量为 0
        for (int a = 0; a < n; a++) {
            for (int b = 0; b < m; b++) {
                if (board[a][b] == '1') {  // 如果是陆地
                    int idx = index(a, b);  // 计算索引
                    father[idx] = idx;  // 初始化父节点为自身
                    sets++;  // 每个 '1' 都是一个独立的岛屿
                }
            }
        }
    }

    // 将二维坐标转换为一维索引
    int index(int a, int b) {
        return a * cols + b;
    }

    // 查找并查集的根节点，并进行路径压缩
    int find(int i) {
        if (i != father[i]) {
            father[i] = find(father[i]);
        }
        return father[i];
    }

    // 合并两个集合
    void unionSets(int a, int b, int c, int d) {
        int fx = find(index(a, b));
        int fy = find(index(c, d));
        if (fx != fy) {  // 如果不是同一集合，则合并
            father[fx] = fy;
            sets--;  // 合并后，岛屿数量减少
        }
    }
};